1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <cstdio>
#define LL long long
const int maxn = 1005;
const LL mo = 1e9 + 7;
using namespace std;
int n, m, cnt[2], lnk[2], V;
char str[maxn][maxn]; LL k;
LL pow(LL x, LL t){
LL res = 1; x %= mo;
while (t > 0){
if (t & 1) res = res * x % mo;
x = x * x % mo;
t >>= 1;
}
return res;
}
int main(){
scanf("%d%d%lld", &n, &m, &k);
for (int i = 1; i <= n; i++) scanf("%s", str[i] + 1);
for (int i = 1; i <= n; i++)
if (str[i][1] == '#' && str[i][m] == '#') cnt[0]++;
for (int j = 1; j <= m; j++)
if (str[1][j] == '#' && str[n][j] == '#') cnt[1]++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++){
V += (str[i][j] == '#');
if (str[i][j] == '#' && str[i][j + 1] == '#') lnk[0]++;
if (str[i][j] == '#' && str[i + 1][j] == '#') lnk[1]++;
}
if (cnt[0] == 0 && cnt[1] == 0){
printf("%lld\n", pow(V, k - 1));
return 0;
}
if (cnt[0] > 0 && cnt[1] > 0){
puts("1"); return 0;
}
if (cnt[0] > 0){
LL ans = pow(V, k - 1) - 1ll * lnk[0] * (pow(V, k - 1) - pow(cnt[0], k - 1)) % mo * pow(V - cnt[0], mo - 2) % mo;
printf("%lld\n", (ans + mo) % mo);
}
if (cnt[1] > 0){
LL ans = pow(V, k - 1) - 1ll * lnk[1] * (pow(V, k - 1) - pow(cnt[1], k - 1)) % mo * pow(V - cnt[1], mo - 2) % mo;
printf("%lld\n", (ans + mo) % mo);
}
return 0;
}
|